home *** CD-ROM | disk | FTP | other *** search
/ Aminet 7 / Aminet 7 - August 1995.iso / Aminet / docs / misc / ConcNews.lha / news / general.programming / comp.programming_1573_000023.msg < prev    next >
Encoding:
Internet Message Format  |  1994-11-27  |  1.9 KB
  1. Path: dd.chalmers.se!news.chalmers.se!sunic!EU.net!howland.reston.ans.net!europa.eng.gtefsd.com!library.ucla.edu!csulb.edu!paris.ics.uci.edu!news.claremont.edu!kaiwan.com!kaiwan!preston
  2. From: preston@kaiwan.com (Preston L. Bannister)
  3. Newsgroups: comp.programming
  4. Subject: Re: Hash function for strings
  5. Date: 3 Mar 1994 13:05:53 -0800
  6. Organization: Upstanding Systems
  7. Lines: 41
  8. Message-ID: <preston.762728626@kaiwan>
  9. References: <amundsj.1.0@novell.oih.no>
  10. NNTP-Posting-Host: kaiwan.kaiwan.com
  11.  
  12. In <amundsj.1.0@novell.oih.no> amundsj@novell.oih.no (AMUNDSEN JARLE/3AA/D) writes:
  13.  
  14. >I am trying to find a good hash function for strings, names that is, and
  15. >wonder if anyone has an idea on how good such a function can hash. Given
  16. >that the keys are not known in advance.
  17.  
  18. >The keys I used in the test were all different, 1500 in all, and the size
  19. >of the hash table was 6001. At best, a hash function supplied a unique
  20. >adress to 75% of the keys, while the rest collided.
  21.  
  22. I'm rather fond of a simple hash function published in the
  23. Communications of the ACM a few years back (sorry, no reference).
  24.  
  25. Briefly the function is:
  26.  
  27.     char t[256];    /* contains the values 0..255 randomly shuffled */
  28.  
  29.     char hash(const char* s) {
  30.         char h = 0;
  31.         while (*s) {
  32.             h = t[h ^ *s++];
  33.         }
  34.         return h;
  35.     }
  36.  
  37. The downside is that this only generates small hash keys (0..255).
  38.  
  39. The upside is that hash function is _very_ cheap, and tends to
  40. generate a very uniform distribution of hash keys.  Also, strings that
  41. hash to the same value tend to be very dissimilar, so searching a hash
  42. bucket (for instance) is quite fast as the strings miscompare in the
  43. first few characters.
  44.  
  45. You can generate bigger hash keys by running the hash function more
  46. than once, with a different initial value for h, and concatenating the
  47. results.  This can be faster than running a more complex hash function
  48. just once.
  49. -- 
  50. Preston L. Bannister 
  51. Upstanding Systems
  52. preston@kaiwan.com
  53.